import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// https://leetcode.cn/problems/combination-sum-ii/
public class combinationSum2 {
    class Solution {
        private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            backTracking(new ArrayList<>(),0,candidates,target);
            return res;

        }


        private void backTracking(List<Integer> path , int start , int [] candidates, int sum)
        {
            if(sum == 0)
            {
                res.add(new ArrayList<>(path));
                return ;
            }
            int pre = 0x3f3f3f3f;
            for(int i = start ; i < candidates.length && sum >= candidates[i] ; i++)
            {
                if(candidates[i] == pre) continue;
                pre = candidates[i];
                path.add(candidates[i]);
                backTracking(path,i + 1, candidates,sum - candidates[i]);
                path.remove(path.size()-1);

            }

        }
    }
}
